package it.storm.solution;

/**
 * 1779. 找到最近的有相同 X 或 Y 坐标的点
 * https://leetcode-cn.com/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate/
 */
public class Solutions_1779 {
    public static void main(String[] args) {
//        int x = 3, y = 4;
//        int[][] points = {{1, 2}, {3, 1}, {2, 4}, {2, 3}, {4, 4}};  // output: 2

//        int x = 3, y = 4;
//        int[][] points = {{3, 4}};  // output: 0

        int x = 3, y = 4;
        int[][] points = {{2, 3}};  // output: -1

        int result = nearestValidPoint(x, y, points);
        System.out.println(result);
    }

    public static int nearestValidPoint(int x, int y, int[][] points) {
        int res = -1;
        int minDist = Integer.MAX_VALUE;
        for (int i = 0; i < points.length; i++) {
            int[] point = points[i];
            if (point[0] == x || point[1] == y) {
                // x 坐标和 y 坐标至少有一个相同，说明 point 坐标有效
                int distance = Math.abs(point[0] - x) + Math.abs(point[1] - y);
                if (distance == 0) {
                    // 曼哈顿距离为 0 时，提前返回结果
                    return i;
                }
                if (distance < minDist) {
                    res = i;
                    minDist = distance;
                }
            }
        }
        return res;
    }
}
